15.2 並行GC用のバリア技法
shade: 白いオブジェクトを灰色にする。他の色については何もしない。
scan: そのオブジェクトを走査して黒にして、境界を進める。
revert: 黒のオブジェクトを灰色に戻して境界を後退させる。子をまた走査することになるので白を追加されても迷子にならない。
境界: スキャンされてるところのフロンティアライン
これ以外のことをすると不変条件が壊れる。
オブジェクトを白に戻したり(突然白にするということ？(自明にやばそう))
走査せずに黒くする(子が色つけられなかったりして死)
アルゴリズム15-1 灰色
code:アルゴリズム15-1-a.py
def atomic Write(src, i, ref):
if isBlack(src):
if isWhite(ref):
revert(src)
code:アルゴリズム15-1-b.py
def atmic Write(src, i, ref):
if isBlack(src):
revert(src)
code:アルゴリズム15-1-c.py
def atomic Write(src, i, ref):
if isBlack(src)
shade(ref)
挿入バリア(著者曰く「インクリメンタルアップデートバリア」より適切な用語)を用いて不変条件を保つ。
黒いオブジェクトに白いポインタを格納するのを防ぐ。
ルートオブジェクトは灰色なのでリードバリヤは不要。 ← これはどういうこと？
インクリメンタルアップデート技法である。
全ての技法(多分15-1と15-2の中で)で最高の精度。
ヤバい追加がなされた時に、境界を戻すことで解決。
再び走査がsrcに到達した際にrefに色が塗られる。
精度は高いが、境界を戻すので、進行が遅くなる。
15-1-aの変形。
refがwhiteじゃないヤバい状況ではない時でもrevertする。
当然精度は下がるけど実装をサボれるということ？
15-1-aより精度が低い。
精度が低いものの、走査は進んでいくので境界を進める上での利点はある。
後からrefが消えるような場合でも灰色にしてしまったので回収できない。
isBlackのチェックをサボるとatomic性が緩まる(ストアとshadeの順序が保たれるだけでよい)。
アルゴリズム15-2 黒色
code:アルゴリズム15-2-a.py
def atomic Read(src, i):
if isGray(src):
ref = shade(ref)
return ref
code:アルゴリズム15-2-b.py
def atomic Read(src, i):
if isGray(src):
scan(src)
code:アルゴリズム15-2-c.py
def atomic Write(src, i, ref):
if isGray(src) || isWhite(src):
最初2つは黒いミューテータから白いポインタが出てくることを防ぐ。
不変条件: 黒いミューテータが扱うポインタは黒または灰
3つ目は弱い不変条件を保つ。灰色保護されているポインタを消してしまうことを防ぐ。
15-1-cより低精度。後で消えるオブジェクトまでshadeしてしまうかもだから。
元々はコピーGC用に作られた。色付けはfrom空間からto空間へのコピーを意味するのでshadeするとto空間へのポインタを返す。
灰色から白が取れなくする。
15-2-aの低精度な変形。
OSの仮装記憶のトラップで色を判別してできる？
灰色を取れなくする。
湯浅先生も独立に考案
D2とかZとかSとかって何？ ← 図15-2の名前
これらの中で精度は最悪。
サイクル中に到達不能になったものを回収できない。
バリア技法の完全性
これらの技法にアルゴリズム15-3のリード/ライトバリアを加えると可能なアプローチの全体をカバーしていることになる(らしい)(←つまりこの7パターンのどれかでしか不変条件を守るバリアは実現できない ということ？)。
これを使うことで以下の弱い不変条件を守れる。
全ての黒から白へのポインタについて、その白のオブジェクトはどこかで灰色のオブジェクトから指されていること
これはもとの弱い不変条件よりわずかに強い条件。
code:アルゴリズム15-3.py
def atomic Read(src, i):
if isWhite(src):
shade(ref)
return ref
def atomic Write(src, i, ref):
if isGray(src):
灰の子が白だった時には灰色に塗っておくことで、図15-2のbの時のパターンみたいな時にヤバくないようにする。
このリードバリアによって、白のポインタのチェーンをたどっていくと、灰と白の交互の縞模様になって、灰色保護の長さが高々2になる。
したがって、灰が直接指す白のポインタが切れることによる不変条件の破壊さえライトバリアで防げばよい。
いろんなバリエーションが考えられる。
灰色にするんじゃなくて直ちに走査して黒くする。
Writeバリアで削除されるポインタの入ってるソースオブジェクトを走査して黒くする ← これどういうこと？
Readバリアで色付けするかわりに走査する。
15-2-a → 15-2-b の変形
挿入されるポインタのターゲットを色つけるかわりに灰色にする(15-3？)。
不変条件を守る変形でバリエーションができるね。
並行ライトバリアのメカニズム
不変条件を守るためにはライトバリアでポインタ書き込みを監視して灰色オブジェクトを何らかのデータ構造に記録していく。
記録する方法の1つとしてログへの追記がある。
11章でやったカードテーブルを使ってやっていく。
11.8のP238にカードテーブルがあった！
チャンクみたいなカードに分割してやり、ライトバリアがオブジェクトが灰色だとセットするのに、カードテーブルにフラグを書く(ダーティーにする)。
コレクタはダーティーなカードを走査して灰色オブジェクトを追跡し、おわったらテーブルのフラグを消す(クリーンにする)。
カードごとに灰色オブジェクトとして扱ってしまうようなバリア(15-?-?)では、生きてるオブジェクトの周辺のごみを回収できないので精度が低いかと思われるが、実際には問題にはならない。
カードテーブルをクリーンにしていき、全部クリーンにするのがコレクタの1サイクルでの仕事。
全部クリーンにするまでやるかわりにストップザワールドでやるという方法もあるらしいが微妙らしい。
1レベルカードテーブル
今まで書いてたのが1レベルのテーブル。
カードのステータスは
dirty
refining
clean
の3つを取る。
ミューテータのライトバリアは(shadeする時)状態をdirtyにする。
この時にCASのようなことはせずに単にストア命令を使う。
コレクタがカードを舐める時はrefiningにセットしてから探索して、新たな状態を不可分setで(多分)cleanにしようとする。
成功したら: cleanになった。
失敗したら: 他のライトバリアがdirtyにしようとしたということなので、また走査するべき灰色オブジェクトがこのカードに入れられたということがわかる。その場でまたやりなおせるが、後回しにしたほうがよさそう。
11章参照(P243 カードの要約)で要約することもできるらしい。
2レベルカードテーブル
ほとんどのカードはcleanなので、2レベルのテーブルでdirtyなカードを高速にみつけられるようになるかも。
実はややこしい問題があってカードの束がクリーンであることをsetするのにはフェンス命令がいるかもしれない。
作業量の削減
その1
同じオブジェクトを何回も走査するのをやめたい。
他にコレクタが追跡する作業があるうちはカードのクリーニングを遅延する。
15-1-aスタイルのバリアを使って、dirtyなカードの上のオブジェクトの追跡をサボってやり、カードをクリーンにする時にはじめて追跡する。
要するにdirtyを後回しにする。どうせdirtyなカードの上のものは後でやりなおす必要があるから？
走査の回数が減るし、キャッシュミスも減る。
その2
dirtyなカードの数を減らす。
15-1-aでrevertが本当に必要なのはsrcが既に追跡されてる時だけ。
未追跡なら、単に書き換えておけば後で追跡された時に子も追跡される。
色のチェックはWriteのたびにやるには大変な操作なので、カードのstatusで判別していきたい。
code:dirty.py
for each C in dirty card:
if not isTraced(C): $ # 「もう1つのテーブル」なるものを見に行く
setClean(C) # まだtraceが終わってなかったら、どうせあとで見るのでcleanと思っててもいい。
if isTraced(C):
setDirty(C) # あとで見ると思ってたけど、この間に実は見終ってたらマズいことになるのでdirtyに戻す。
kindleと紙の本でindentが違う！
若い世代のオブジェクトはどんどん書き換えられるので、あと回しにしたほうが良さそう。